#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int  **res;	//保存排列结果
int *path;  // 
int pathlen, cnt;
void backtrack(int start, int arr[], int len, int k, int** returnColumnSizes)
{
	if (pathlen == k) {
        //printf("%d:%d %d\n",cnt,path[0],path[1]);	    
        res[cnt] = malloc(sizeof(int) * pathlen);
        memcpy(res[cnt], path, sizeof(int) * pathlen);
        (*returnColumnSizes)[cnt] = pathlen;
		cnt++;
		return ;
	}

	for (int i = start; i < len; i++) {	// 横向遍历
		path[pathlen++] = arr[i]; // 选择数字

		backtrack(i+1, arr, len, k, returnColumnSizes);  //纵向遍历

		pathlen--;
	}
}


int combinate(int n, int m)
 {
 	m = (m > n/2)? (n-m):m;
 	long ret = 1, m_fac = 1;
    int i;
    //例如：C10取3
    for (i = m; i > 1; i--) { //3!
        m_fac *= i;
    }
 	for (i = n; i > (n-m); i--) {  //10*9*8  
 		ret *= i;
 	}
     
 	ret /= m_fac;
 	return ret;
 }

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
	int nums[n];
    for (int i = 0; i < n; i++) nums[i] = i+1;
    
    int N = combinate(n, k);    //组合
    // printf("combinate(n, k):%d\n", N);
	res = malloc(sizeof(int *) * N);	//全局变量
    *returnColumnSizes = malloc(sizeof(int) * N);

	path = malloc(sizeof(int)*k);	//保存解
	cnt = 0; pathlen = 0;

	backtrack(0, nums, n, k, returnColumnSizes);
    *returnSize = cnt;
    free(path); 
    return res;
}


void print_matrix(int **matrix, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			printf("%d ",matrix[i][j]);
		printf("\n");
	}
}
int main()
{
	int arr[4] = {1,2,3,4};
	int temp1, *temp2;
	combine(4,2, &temp1, &temp2);
	print_matrix(res, temp1, 2);
	return 0;
}